package leetcode.editor.cn;

//[70]爬楼梯
public class ClimbingStairs70 {
    public static void main(String[] args) {
        Solution solution = new ClimbingStairs70().new Solution();
        System.out.println("ClimbingStairs70:main:"+solution.climbStairs(3));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //	执行耗时:0 ms,击败了100.00% 的Java用户
        //	内存消耗:39.5 MB,击败了6.52% 的Java用户
        public int climbStairs(int n) {
            if (n < 2) return n;
            //fn = fn-1 + fn-2
//            int[] dp = new int[n + 1];
//            dp[0] = 1;
//            dp[1] = 1;
//            for (int i = 2; i <= n; i++) {
//                dp[i] = dp[i-1]+dp[i-2];
//            }
//            return dp[n];

            //	执行耗时:0 ms,击败了100.00% 的Java用户
            //	内存消耗:39.4 MB,击败了39.09% 的Java用户
            // 减少内存消耗。ON->O1
            int pre0 = 1;
            int pre1 = 1;
            int cur = 0;
            for (int i = 2; i <= n; i++) {
                cur = pre1 + pre0;
                //保存前 2个数。
                pre0 = pre1;
                pre1 = cur;
            }
            return cur;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}